import java.util.Arrays;

public class ShellSort {
    static void shellSort(int[] arr){
        if(arr == null || arr.length == 0)
            return ;
        int gap= arr.length/2;
        while (gap>=1){
            shell(arr,gap);
            gap/=2;
        }
    }

    private static void shell(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i+=gap) {
            int target=arr[i];
            int j=i;
            while (j>0&&arr[j-gap]>target){
                arr[j]=arr[j-gap];
                j-=gap;
            }
            arr[j]=target;
        }
    }
    public static void main(String[] args) {
        int[] arr=new int[]{9, 8, 5, 6, 7, 5, 6, 2, 4, 98, 5, 87, 2, 6, 2, 0, 5, 5, 9};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
